// synch.cc 
//	Routines for synchronizing threads.  Three kinds of
//	synchronization routines are defined here: semaphores, locks 
//   	and condition variables (the implementation of the last two
//	are left to the reader).
//
// Any implementation of a synchronization routine needs some
// primitive atomic operation.  We assume Nachos is running on
// a uniprocessor, and thus atomicity can be provided by
// turning off interrupts.  While interrupts are disabled, no
// context switch can occur, and thus the current thread is guaranteed
// to hold the CPU throughout, until interrupts are reenabled.
//
// Because some of these routines might be called with interrupts
// already disabled (Semaphore::V for one), instead of turning
// on interrupts at the end of the atomic operation, we always simply
// re-set the interrupt state back to its original value (whether
// that be disabled or enabled).
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "synch.h"
#include "system.h"

//----------------------------------------------------------------------
// Semaphore::Semaphore
// 	Initialize a semaphore, so that it can be used for synchronization.
//
//	"debugName" is an arbitrary name, useful for debugging.
//	"initialValue" is the initial value of the semaphore.
//----------------------------------------------------------------------

Semaphore::Semaphore(char* debugName, int initialValue)
{
    name = debugName;
    value = initialValue;
    queue = new List;
}

//----------------------------------------------------------------------
// Semaphore::Semaphore
// 	De-allocate semaphore, when no longer needed.  Assume no one
//	is still waiting on the semaphore!
//----------------------------------------------------------------------

Semaphore::~Semaphore()
{
    delete queue;
}

//----------------------------------------------------------------------
// Semaphore::P
// 	Wait until semaphore value > 0, then decrement.  Checking the
//	value and decrementing must be done atomically, so we
//	need to disable interrupts before checking the value.
//
//	Note that Thread::Sleep assumes that interrupts are disabled
//	when it is called.
//----------------------------------------------------------------------

void
Semaphore::P()
{
    IntStatus oldLevel = interrupt->SetLevel(IntOff);	// disable interrupts
    
    while (value == 0) { 			// semaphore not available
	queue->Append((void *)currentThread);	// so go to sleep
	currentThread->Sleep();
    } 
    value--; 					// semaphore available, 
						// consume its value
    
    (void) interrupt->SetLevel(oldLevel);	// re-enable interrupts
}

//----------------------------------------------------------------------
// Semaphore::V
// 	Increment semaphore value, waking up a waiter if necessary.
//	As with P(), this operation must be atomic, so we need to disable
//	interrupts.  Scheduler::ReadyToRun() assumes that threads
//	are disabled when it is called.
//----------------------------------------------------------------------

void
Semaphore::V()
{
    Thread *thread;
    IntStatus oldLevel = interrupt->SetLevel(IntOff);

    thread = (Thread *)queue->Remove();
    if (thread != NULL)	   // make thread ready, consuming the V immediately
	scheduler->ReadyToRun(thread);
    value++;
    (void) interrupt->SetLevel(oldLevel);
}

// Dummy functions -- so we can compile our later assignments 
// Note -- without a correct implementation of Condition::Wait(), 
// the test case in the network assignment won't work!

//--------------------------------------------------------------------
// Lock::Lock()
// Constructor for creating a lock, Set lock to FREE
// (Kevin)
//--------------------------------------------------------------------
Lock::Lock(char* debugName) 
{
	name = debugName;
	lockState = FREE;
	lockWaitingQueue = new List();
}
//--------------------------------------------------------------------
// Lock::~Lock()
// Deallocate members from Lock class
// (Kevin)
//--------------------------------------------------------------------
Lock::~Lock() 
{
 	delete lockWaitingQueue;
}
//--------------------------------------------------------------------
// Lock::Acquire()
// This method will obtain the lock and change the state of the lock
// to BUSY, if the lock is FREE. Whoever is next in the queue to get
// the lock should be able to own it and set the state to BUSY.
// (Kevin)
//--------------------------------------------------------------------
void Lock::Acquire() 
{
	// disable interrupts
	IntStatus oldLevel = interrupt->SetLevel(IntOff);
	// perform tasks in here
	if(isHeldByCurrentThread())
	{
		// restore interrupts
		(void) interrupt->SetLevel(oldLevel);
		return;
	}
	if(lockState == FREE)
	{
		lockState = BUSY;
		lockOwner = currentThread;
		//printf("Lock %s was ACQUIRED by %s.\n", name ,lockOwner->getName());
	}
	else
	{
		//printf("%s going on %s waiting queue\n", currentThread->getName(), name);
		lockWaitingQueue->Append(currentThread); // add myself lock waiting queue and go to sleep
		currentThread->Sleep();
	}
	// restore interrupts
	(void) interrupt->SetLevel(oldLevel);
}
//--------------------------------------------------------------------
// Lock::Release()
// This method will set the lock to FREE because the thread is finished
// with its execution stream. Also need to wake up a thread that is
// waiting for acquire.
// (Kevin)
//--------------------------------------------------------------------
void Lock::Release() 
{
	// disable interrupts
	IntStatus oldLevel = interrupt->SetLevel(IntOff);
	// perform tasks in here
	if(!isHeldByCurrentThread())
	{
		// restore interrupts
		//printf("Lock is not held by %s. Restoring interrupts\n",currentThread->getName());
		(void) interrupt->SetLevel(oldLevel);
		return;
	}
	if(!lockWaitingQueue->IsEmpty())
	{
		// remove a thread from this lock's wait queue
		Thread* ptrThread = (Thread*)lockWaitingQueue->Remove();
		//printf("%s released lock %s. Giving %s the lock\n", currentThread->getName(), name, ptrThread->getName());
		// put it  in the readyQueue in ready state, make them lock owner
		scheduler->ReadyToRun(ptrThread);
		lockOwner = ptrThread;
	}
	else
	{
		//printf("%s released lock %s. Nobody is waiting for lock\n\n", currentThread->getName(), name);
		lockState = FREE;
		lockOwner = NULL;
	}
	// restore interrupts
	(void) interrupt->SetLevel(oldLevel);
}
//--------------------------------------------------------------------
// Lock::isHeldByCurrentThread()
// return true if the current thread holds the lock and if not 
// return false
// (Kevin)
//--------------------------------------------------------------------
bool Lock::isHeldByCurrentThread()
{
	if(lockOwner == currentThread)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool Lock::hasWaitingThreads()
{
	if(!lockWaitingQueue->IsEmpty())
	{
		return true;
	}
	return false;
}

//-----------------------------------------------------------------
// Lock::isFree()
// returns true if the lock is FREE, returns false if the lock is
// busy.
//-----------------------------------------------------------------
bool Lock::isFree()
{
	if(lockState == FREE)
	{
		return true;
	}
	return false;
}

//--------------------------------------------------------------------
// Condition::Condition
// Constructor for condition
// (Kevin)
//--------------------------------------------------------------------
Condition::Condition(char* debugName) 
{ 
	name = debugName;
	waitingLock = NULL;
	waitingLockQueue = new List();
}
//--------------------------------------------------------------------
// Condition::~Condition()
// release memory
// (Kevin)
//--------------------------------------------------------------------
Condition::~Condition() 
{ 
	delete waitingLockQueue;
}
//-------------------------------------------------------------------
// Condition::Wait(Lock* conditionLock)
// Tells the thread to wait on a specific condition. The lock is 
// then released, thread goes to sleep, and attempts to Acquire
// when woken up.
// (Kevin)
//-------------------------------------------------------------------
void Condition::Wait(Lock* conditionLock) 
{ 
	// disable interrupts
	IntStatus oldLevel = interrupt->SetLevel(IntOff);
	if(conditionLock == NULL)
	{
		printf("ERROR lock being passed in is NULL\n");
		(void) interrupt->SetLevel(oldLevel);
		return;
	}
	if(waitingLock == NULL)
	{
		waitingLock = conditionLock;
	}
	if(waitingLock != conditionLock)
	{
		printf("ERROR lock passed in is not the waitingLock\n");
		// restore interrupts
		(void) interrupt->SetLevel(oldLevel);
		return;
	}
	waitingLockQueue->Append(currentThread);
	//printf("%s is WAITING on %s.\n", currentThread->getName(), name);
	conditionLock->Release();
	//printf("*** GOING TO SLEEP \n");
	currentThread->Sleep();
	//printf("WENT TO SLEEEEEEEP\n");
	conditionLock->Acquire();
	//printf("%s got lock %s\n", currentThread->getName(), name);
	// restore interrupts
	(void) interrupt->SetLevel(oldLevel);
	//ASSERT(FALSE);
}
//-------------------------------------------------------------------
// Condition::Signal(Lock* conditionLock)
// Tells the thread to signal a specific condition. The lock is 
// then given back to the thread that was waiting.
// (Kevin)
//-------------------------------------------------------------------
void Condition::Signal(Lock* conditionLock) 
{ 
	// disable interrupts
	IntStatus oldLevel = interrupt->SetLevel(IntOff);
	if(waitingLockQueue->IsEmpty())
	{
		// restore interrupts
		//printf("Waiting Lock Queue is EMPTY\n");
		(void) interrupt->SetLevel(oldLevel);
		return;
	}
	if(waitingLock != conditionLock)
	{	
		printf("ERROR lock passed in is not the same as waitingLock\n");
		// restore interrupts
		(void) interrupt->SetLevel(oldLevel);
		return;
	}
	//if(!waitingLock->isFree())
	//{
	//	waitingLock->Release();
	//}
	Thread* ptrThread = (Thread*)waitingLockQueue->Remove();
	//printf("%s SIGNALLED by %s.\n", name, currentThread->getName());
	scheduler->ReadyToRun(ptrThread);
	if(waitingLockQueue->IsEmpty())
	{
		waitingLock = NULL;
	}
	// restore interrupts
	(void) interrupt->SetLevel(oldLevel);
}
//-------------------------------------------------------------------
// Condition::Broadcast(Lock* conditionLock)
// Tell all threads that were waiting on the condition to wait up. 
// Just signals all threads in the waiting lock queue.
// (Kevin)
//-------------------------------------------------------------------
void Condition::Broadcast(Lock* conditionLock) 
{ 
	while(!waitingLockQueue->IsEmpty())
	{
		Signal(conditionLock);
	}
}

bool Condition::WaitingQueueIsEmpty()
{
	if(waitingLockQueue->IsEmpty())
	{
		return true;
	}
	return false;
}
